package com.zhaopin.theswordreferstooffer;

import javax.xml.bind.SchemaOutputResolver;

/**
 * @author yin.peide
 * @date 2021-06-24 10:45
 * 面试题:39 平衡二叉树
 * 解法1： 使用递归的方法即可 时间复杂度高 //TODO 再看
 * 解法2： 还是一种递归，但是只会遍历一次
 * <p>
 * 平衡树定义： 如果一个节点的下面两个节点的深度 差值超过1 则不是平衡树了，否则是平衡树
 */
public class Offer39 {


    public static void main(String[] args) {
        TreeNode treeNode3 = new TreeNode(3);
        TreeNode treeNode9 = new TreeNode(9);
        TreeNode treeNode20 = new TreeNode(20);
        TreeNode treeNode14 = new TreeNode(14);
        TreeNode treeNode15 = new TreeNode(15);
        TreeNode treeNode7 = new TreeNode(7);

        treeNode3.setLeft(treeNode9);
        treeNode3.setRight(treeNode20);
        treeNode20.setLeft(treeNode7);
        treeNode20.setRight(treeNode15);
        treeNode15.setRight(treeNode14);


//        System.out.println(maxDepth(treeNode3));
//
//        System.out.println(maxDepthLeft(treeNode3));
//        System.out.println(maxDepthRitht(treeNode3));
        System.out.println(isBalanced(treeNode3));
    }

    public static int maxDepth(TreeNode root) {
        return root == null ? 0 : Math.max(maxDepth(root.getLeft()), maxDepth(root.getRight())) + 1;
    }

    public static int maxDepthLeft(TreeNode root) {
        return root == null ? 0 : maxDepth(root.getLeft()) + 1;
    }

    public static int maxDepthRitht(TreeNode root) {
        return root == null ? 0 : maxDepth(root.getRight()) + 1;
    }

    /**
     * 是否是平衡二叉树
     *
     * @param root
     * @return
     */
    public static boolean isBalanced(TreeNode root) {
        int rootInt = height(root);
        return rootInt >= 0;
    }

    public static int height(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int leftHeight = height(root.getLeft());
        int rightHeight = height(root.getRight());
        if (leftHeight == -1 || rightHeight == -1 || Math.abs(leftHeight - rightHeight) > 1) {
            return -1;
        } else {
            return Math.max(leftHeight, rightHeight) + 1;
        }
    }
}
